module Diccionario (Diccionario, vacio, definir, definirVarias, obtener, claves) where

import Maybe
import List
import Arbol23

{- Definiciones de tipos. -}

type Comp clave = clave->clave->Bool
type Estr clave valor = Arbol23 (clave,valor) clave

data Diccionario clave valor = Dicc {cmp :: Comp clave, estructura :: Maybe (Estr clave valor)}
--El comparador es por menor.

instance (Show a, Show b) => Show (Diccionario a b) where
    show (Dicc cmp estr) = case estr of
									Nothing	  -> "VACIOPAN"
									otherwise -> show estr


{- Funciones provistas por la cátedra. -}

--Inserta un nuevo par clave, valor en una estructura que ya tiene al menos un dato.
insertar :: clave -> valor -> Comp clave -> Estr clave valor -> Estr clave valor
insertar c v comp a23 = interceptar (insertarYPropagar c v comp a23) id (\s1 (c1, s2)->Dos c1 s1 s2)

--Maneja el caso de que la segunda componente sea Nothing.
interceptar :: (a, Maybe b) -> (a -> c) -> (a -> b -> c) -> c
interceptar (x,y) f1 f2 = case y of
			       Nothing -> f1 x
			       Just z -> f2 x z

{- Inserta una clave con su valor correspondiente. Si se actualiza el índice, el cambio se propaga hacia arriba
   para mantener balanceado el Arbol.
   Usamos recursión explícita porque este tipo de recursión no es estructural (no se aplica a todos los hijos). -}
insertarYPropagar :: clave -> valor -> Comp clave -> Estr clave valor -> (Estr clave valor, Maybe (clave, Estr clave valor))
insertarYPropagar c v comp a23 = let rec = insertarYPropagar c v comp in case a23 of
	--Si es hoja, elegimos la máxima de las claves y propagamos el balanceo hacia arriba.
	Hoja (ch,vh) -> if comp c ch 
				then (Hoja (c,v), Just (ch, Hoja (ch,vh)))
				else (Hoja (ch, vh), Just (c, Hoja (c,v)))
	{- Si el actual es Nodo-Dos, o se queda en forma Nodo-Dos o se transforma en 
	   Nodo-Tres; no puede ocurrir que haya propagación hacia arriba (retornamos Nothing). -}
	Dos c1 a1 a2 -> (if comp c c1
				then 
				-- La clave c va del lado izquierdo.
					interceptar (rec a1) 
						(\s1 -> Dos c1 s1 a2)
						(\s1 (c3, s2) -> Tres c3 c1 s1 s2 a2)
				else 
				-- La clave c va del lado derecho.
					interceptar (rec a2) 
						(\s1 -> Dos c1 a1 s1)
						(\s1 (c3, s2) -> Tres c1 c3 a1 s1 s2), Nothing)
	{- Nodo-tres sólo propaga si de abajo propagan, los tres casos son muy similares
	   Sólo cambia en que Arbol se inserta. -}
	Tres c1 c2 a1 a2 a3 -> if comp c c1
				then 
					-- La clave debe ir en el primer Arbol.
					interceptar (rec a1) 
						(\s1 -> (Tres c1 c2 s1 a2 a3, Nothing))
						(\s1 (c3, s2) -> (Dos c3 s1 s2, Just(c1, Dos c2 a2 a3)))
				else if comp c c2
				then 
					-- La clave debe ir en el Arbol del medio.
					interceptar (rec a2) 
						(\s1 -> (Tres c1 c2 a1 s1 a3, Nothing))
						(\s1 (c3, s2) -> (Dos c1 a1 s1, Just(c3, Dos c2 s2 a3)))
				else 
					--La clave debe ir en el último Arbol.
					interceptar (rec a3) 
						(\s1 -> (Tres c1 c2 a1 a2 s1, Nothing))
						(\s1 (c3, s2) -> (Dos c1 a1 a2, Just(c2, Dos c3 s1 s2)))

--Se asume que la lista no tiene claves repetidas.

definirVarias::[(clave,valor)]->Diccionario clave valor->Diccionario clave valor
definirVarias = (flip.foldr.uncurry) definir


{- Funciones a implementar. -}

-- Ejercicio 6

-- La función vacio crea un diccionario vacío (estructura es Nothing) con la función de comparación pasada como parámetro.
vacio :: Comp clave -> Diccionario clave valor
vacio c = Dicc c Nothing


-- Ejercicio 7

-- La función definir define una clave con su valor correspondiente en el diccionario.
-- Si el diccionario está vacío (estructura es Nothing), devuelve un nuevo diccionario donde la estructura es una hoja cuyo valor es un par del tipo (clave, valor).
-- Si no, utiliza la función insertar provista por la cátedra para insertar un nuevo par del tipo (clave, valor) en la estructura existente.
definir :: clave -> valor -> Diccionario clave valor -> Diccionario clave valor
definir c v (Dicc cmp estr) = Dicc cmp (Just new_estr)
	where new_estr = case estr of
						Nothing   -> Hoja (c, v)
						Just estr -> insertar c v cmp estr


-- Ejercicio 8

-- La función obtener busca una clave en el diccionario y devuelve su valor correspondiente, o Nothing si la clave no se encuentra definida.
-- Usa la función auxiliar hojaBuscada para obtener una hoja (en donde debería estar la clave buscada en caso de estar definida) y verifica si las claves coinciden.
-- La función hojaBuscada siempre devuelve una hoja, pero usamos case con un único caso para poder obtener el valor de esa hoja.
-- Dado que la definición debe ser buscada en una hoja, la complejidad de la función obtener será la de la función hojaBuscada.
obtener :: Eq clave => clave -> Diccionario clave valor -> Maybe valor
obtener clave_buscada (Dicc cmp Nothing) = Nothing
obtener clave_buscada (Dicc cmp (Just a23)) = if clave_buscada == fst definicion then Just (snd definicion) else Nothing
	where definicion = case (hojaBuscada cmp clave_buscada a23) of
						Hoja def -> def

-- La función hojaBuscada es auxiliar para obtener.
-- Si la clave buscada está definida en una de las hojas, devuelve esa hoja.
-- Si no, devuelve la hoja en donde debería estar la clave buscada en caso de estar definida.
-- Ya que la evaluación es lazy, el resultado de aplicar la recursión sobre los hijos que no se necesitan no se evalúa, por lo que se "visita" exactamente un nodo por nivel del árbol.
-- Luego, esta función es eficiente: O(h) donde h es la altura de un árbol balanceado con n nodos, es decir, O(log n).
hojaBuscada :: Eq clave => Comp clave -> clave -> Arbol23 valor clave -> Arbol23 valor clave
hojaBuscada cmp clave_buscada = foldA23 Hoja (pasoDeBusquedaEnDos cmp clave_buscada) (pasoDeBusquedaEnTres cmp clave_buscada)

pasoDeBusquedaEnDos :: Eq clave => Comp clave -> clave -> clave -> Arbol23 valor clave -> Arbol23 valor clave -> Arbol23 valor clave
pasoDeBusquedaEnDos cmp clave_buscada clave_nodo a1 a2 = if cmp clave_buscada clave_nodo then a1 else a2

pasoDeBusquedaEnTres :: Eq clave => Comp clave -> clave -> clave -> clave -> Arbol23 valor clave -> Arbol23 valor clave -> Arbol23 valor clave -> Arbol23 valor clave
pasoDeBusquedaEnTres cmp clave_buscada clave_nodo1 clave_nodo2 a1 a2 a3 = if cmp clave_buscada clave_nodo1
																			then a1
																			else if cmp clave_buscada clave_nodo2
																				then a2
																				else a3


-- Ejercicio 9

-- La función claves devuelve una lista con las claves del diccionario.
-- Es similar a la función hojas para árboles 2-3, excepto que devuelve una lista vacía si la estructura es Nothing, y obtiene la primera componente (clave) de cada hoja.
claves :: Diccionario clave valor -> [clave]
claves (Dicc cmp Nothing) = []
claves (Dicc cmp (Just a23)) = foldA23 (\x -> [fst x]) (\_ a1 a2 -> a1 ++ a2) (\_ _ a1 a2 a3 -> a1 ++ a2 ++ a3) a23

{- Diccionarios de prueba: -}

dicc1::Diccionario Int String
dicc1 = definirVarias [(0,"Hola"),(-10,"Chau"),(15,"Felicidades"),(2,"etc."),(9,"a")] (vacio (<))

dicc2::Diccionario String String
dicc2 = definirVarias [("inicio","casa"),("auto","flores"),("calle","auto"),("casa","escalera"),("ropero","alfajor"),("escalera","ropero")] (vacio (<))

dicc3::Diccionario Int String
dicc3 = definirVarias [(0,"Hola"),(-10,"Chau"),(15,"Felicidades"),(2,"etc."),(9,"a")] (vacio (\x y->x `mod` 5 < y `mod` 5))
